import java.util.LinkedList;
import java.util.List;

/**
 * 315. 计算右侧小于当前元素的个数
 *
 * 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 *
 * 示例：
 *
 * 输入：nums = [5,2,6,1]
 * 输出：[2,1,1,0]
 * 解释：
 * 5 的右侧有 2 个更小的元素 (2 和 1)
 * 2 的右侧仅有 1 个更小的元素 (1)
 * 6 的右侧有 1 个更小的元素 (1)
 * 1 的右侧有 0 个更小的元素
 */

/**
 * 利用线段树进行求解
 */
public class Solution_315 {
    public List<Integer> countSmaller(int[] nums) {
        //存放最终结果的
        LinkedList<Integer> res = new LinkedList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        //根据该数据计算线段树根节点的区间
        int start = nums[0],end = nums[0];
        //start始终指向最小的数，end指向最大的数
        for (int i = 0; i < len; i++){
            if (nums[i] < start) {
                start = nums[i];
            }
            if (nums[i] > end) {
                end = nums[i];
            }
        }
        //初始化线段树
        SegmentmapNode root = build(start,end);
        //从右向左遍历数据，并更新线段树，将结果进行头插法
        for (int i = len - 1; i >= 0; i--){
            //因为统计的范围是比该元素小的，所以要 -1
            res.addFirst(count(root,start,nums[i] - 1));
            insert(root,nums[i],1);
        }
        return res;
    }

    /**
     * 线段树节点
     */
    private class SegmentmapNode{
        //区间，count表示落在这个节点上数的个数
        int start,end,count;
        //左右子区间
        SegmentmapNode left,right;
        SegmentmapNode(int start, int end){
            this.start = start;
            this.end = end;
            this.count = 0;
            this.left = null;
            this.right = null;
        }
    }

    /**
     * 递归的构建线段树
     * @param start
     * @param end
     * @return
     */
    private SegmentmapNode build(int start, int end) {
        if (start > end) {
            return null;
        }
        //创建节点
        SegmentmapNode root = new SegmentmapNode(start,end);
        //初始化子节点
        if (start != end) {
            int mid = start + (end - start) / 2;
            root.left = build(start,mid);
            root.right = build(mid+1,end);
        }
        return root;
    }

    /**
     * 递归的统计比它小的数字的个数
     * @param root
     * @param start
     * @param end
     * @return
     */
    private Integer count(SegmentmapNode root, int start, int end) {
        //nums[i] - 1, 排除相等的情况
        //不合法
        if (start > end) {
            return 0;
        }
        //区间一致的时候，即到达叶子节点
        if (start == root.start && end == root.end) {
            return root.count;
        }
        //区间不一致的时候，递归遍历
        int mid = root.start + (root.end - root.start) / 2;
        int leftcount = 0,rightcount = 0;
        //左半边
        if (start <= mid) {
            if (mid < end) {
                //mid < end
                leftcount = count(root.left,start, mid);
            }else {
                //mid == end
                leftcount = count(root.left,start, end);
            }
        }
        //右半边
        if (end > mid) {
            if (start <= mid) {
                //start <= mid
                rightcount = count(root.right,mid + 1, end);
            }else {
                //start == end
                rightcount = count(root.right,start, end);
            }
        }
        return (leftcount + rightcount);
    }

    /**
     * 插入数据并更新所有子节点
     * @param root
     * @param index 下标
     * @param val 加的值
     */
    private void insert(SegmentmapNode root, int index, int val) {
        //到达叶子节点
        if (root.start == index && root.end == index) {
            root.count += val;
            return;
        }

        //递归
        int mid = root.start + (root.end - root.start) / 2;
        //在左半边
        if (index >= root.start && index <= mid){
            insert(root.left,index, val);
        }
        //在右半边
        if (index <= root.end && index > mid){
            insert(root.right,index, val);
        }
        //返回左右子节点的count之和
        root.count = root.left.count +root.right.count;
    }
}
